package com.alg;


import com.algorithm.ListNode;
import com.algorithm.TreeNode;

import java.text.SimpleDateFormat;
import java.util.*;

/**
 * @author: sun.hongliang
 * @create: 2019/12/24 18:30
 */
public class LinkedTest {
    public static void main(String[] args) {
//        ListNode one = new ListNode(4);
//        ListNode two = new ListNode(5);
//        ListNode tree = new ListNode(1);
//        ListNode four = new ListNode(9);
//
//        one.next = two;
//        two.next = tree;
//
//        isPalindrome(one);
//        LinkListPrint.printListNode(one);
        long l = System.currentTimeMillis();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyyMMdd");
        String format = simpleDateFormat.format(new Date(l));
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if ((root.left != null && root.val < root.left.val) || (root.right != null && root.val > root.right.val)) {
            return false;
        }
        return isValidBST(root.left) && isValidBST(root.right);
    }

    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) {
            return new ListNode[0];
        }
        TreeNode root = tree;
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<ListNode> list = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int len = queue.size();
            ListNode h = new ListNode(-1);
            ListNode p = h;
            for (int i = 0; i < len; i++) {
                TreeNode head = queue.pop();
                p.next = new ListNode(head.val);
                p = p.next;
                if (head.left != null) {
                    queue.add(head.left);
                }
                if (head.right != null) {
                    queue.add(head.right);
                }
            }
            list.add(h.next);
        }
        ListNode[] res = new ListNode[list.size()];
        int i = 0;
        for (ListNode l : list) {
            res[i++] = l;
        }
        return res;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }

    private ListNode add(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null)
            return carry == 0 ? null : new ListNode(carry);
        int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
        ListNode node = new ListNode(sum % 10);
        node.next = add(l1 == null ? l1 : l1.next, l2 == null ? l2 : l2.next, sum / 10);
        return node;
    }


    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode f = head;
        ListNode s = head;
        ListNode sn = head.next;
        while (f.next != null && f.next.next != null) {
            f = f.next.next;
            ListNode temp = sn.next;
            sn.next = s;
            s = sn;
            sn = temp;
        }

        if (f.next == null) {
            s = s.next;
        }

        ListNode l = s;
        ListNode r = sn;


        while (l != null && r != null) {
            if (l.val != r.val) {
                return false;
            }
            l = l.next;
            r = r.next;
        }
        return true;
    }


    public static void deleteNode(ListNode node) {
        ListNode first = new ListNode(-1);
        first.next = node;

        ListNode f = node;
        ListNode l = first;
        while (f.next != null && f.next.next != null) {
            l = l.next;
            f = f.next.next;
        }
        l.next = l.next.next;
    }

    public ListNode detectCycle(ListNode head) {
        if (head == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != null && fast != null && fast.next != null) {
            if (slow == fast) {
                return slow;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return null;
    }

    public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode p = head;
        ListNode first = new ListNode(-1);
        ListNode q = first;
        while (p != null) {
            if (!set.contains(p.val)) {
                q.next = p;
            }
            q = p;
            p = p.next;
            q.next = null;
        }
        q.next = null;
        return first.next;
    }

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return null;
        ListNode p = head;
        int len = 1;
        while (p.next != null) {
            len++;
        }
        k = k % len;
        p = head;
        for (int i = 1; i < len - k; i++) {
            p = p.next;
        }
        ListNode nextH = p.next;
        p.next = null;
        ListNode np = nextH;
        for (int i = 1; i < k; i++) {
            np = np.next;
        }
        np.next = head;
        return nextH;
    }

    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode first = new ListNode(-1);
        first.next = head;
        ListNode cr = first;
        ListNode c = cr.next;
        ListNode cn = c.next;
        while (c != null && cn != null) {
            cr.next = cn;
            ListNode temp = cn.next;
            c.next = temp;
            cn.next = c;
            if (temp == null) break;
            cr = c;
            c = temp;
            cn = c.next;
        }

        return first.next;
    }

    public static ListNode swap(ListNode head, int n) {
        if (head == null || head.next == null) return head;
        ListNode first = new ListNode(-1);
        first.next = head;

        ListNode c = head;
        ListNode cr = first;
        ListNode cn = c.next;
        for (int i = 0; i < n; i++) {
            cr = c;
            c = cn;
            cn = cn.next;
        }

        c.next = cn.next;
        cn.next = c;
        cr.next = cn;
        return first.next;
    }

    public static ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode c = head;
        ListNode cn = head.next;
        while (cn != null) {
            ListNode temp = cn.next;
            cn.next = c;
            c = cn;
            cn = temp;
        }
        head.next = null;
        return c;
    }

    public static ListNode deleteDuplicates(ListNode head) {
        ListNode first = new ListNode(-1);
        ListNode c = head;
        ListNode p = first;
        while (c != null) {
            boolean flg = false;
            while (c.next != null && c.val == c.next.val) {
                c = c.next;
                flg = true;
            }
            if (flg) {
                ListNode temp = c;
                c = c.next;
                temp.next = null;
                continue;
            }
            p.next = c;
            p = c;
            c = c.next;
        }
        p.next = null;
        return first.next;
    }


    public static ListNode deleteDuplicates2(ListNode head) {
        ListNode first = new ListNode(-1);
        ListNode c = head;
        ListNode p = first;
        while (c != null) {
            while (c.next != null && c.val == c.next.val) {
                ListNode temp = c;
                c = c.next;
                temp.next = null;
            }
            p.next = c;
            p = c;
            c = c.next;
        }
        p.next = null;
        return first.next;
    }

    public static ListNode partition(ListNode head, int x) {
        ListNode before_head = new ListNode(0);
        ListNode before = before_head;
        ListNode after_head = new ListNode(0);
        ListNode after = after_head;
        while (head != null) {
            if (head.val < x) {
                before.next = head;
                before = before.next;
            } else {
                after.next = head;
                after = after.next;
            }
            head = head.next;
        }
        after.next = null;
        before.next = after_head.next;
        return before_head.next;
    }

    public static ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null) return head;
        if (m == n) return head;
        ListNode first = new ListNode(-1);
        first.next = head;
        ListNode before = first;
        ListNode beforeNext = first.next;
        ListNode after = first;
        ListNode c = head;
        ListNode cn = head.next;
        int i = 1;
        while (c != null) {
            if (i == m - 1) {
                before = c;
                beforeNext = before.next;
                c = c.next;
                cn = c.next;
                i++;
                continue;
            }
            if (i < m) {
                c = c.next;
                cn = c.next;
                i++;
                continue;
            }
            if (i >= m && i <= n - 1) {
                ListNode temp = cn.next;
                cn.next = c;
                c = cn;
                cn = temp;
                i++;
                continue;
            }
            before.next = c;
            beforeNext.next = cn;
            break;
        }
        return first.next;
    }

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode first = new ListNode(-1);
        first.next = head;
        ListNode p = head.next;
        head.next = null;
        while (p != null) {
            ListNode i = first;
            while (i.next != null) {
                if (i.next.val > p.val) {
                    break;
                }
                i = i.next;
            }
            if (i.next == null) {
                i.next = p;
                ListNode t = p.next;
                p.next = null;
                p = t;
            } else {
                ListNode k = p.next;
                ListNode temp = i.next;
                i.next = p;
                p.next = temp;
                p = k;
            }
        }
        return first.next;
    }


    public static ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode first = new ListNode(-1);
        ListNode firstC = first;
        ListNode second = new ListNode(-1);
        ListNode secondC = second;
        ListNode p = head;
        int i = 0;
        while (p != null) {
            if (i == 0) {
                firstC.next = p;
                ListNode temp = p.next;
                firstC = p;
                p.next = null;
                p = temp;
                i = 1;
            } else {
                secondC.next = p;
                ListNode temp = p.next;
                secondC = p;
                p.next = null;
                p = temp;
                i = 0;
            }
        }
        firstC.next = second.next;
        return first.next;
    }


    public static void quickSort(ListNode start, ListNode end) {
        if (start == end) return;
        int k = start.val;
        ListNode p1 = start;
        ListNode p2 = start.next;
        while (p2 != end) {
            if (p2.val < k) {
                p1 = p1.next;
                swapNode(p1, p2);
            }
            p2 = p2.next;
        }
        swapNode(start, p1);
        quickSort(start, p1);
        quickSort(p1.next, end);
    }

    private static void swapNode(ListNode p1, ListNode p2) {
        int temp = p1.val;
        p1.val = p2.val;
        p2.val = temp;
    }

    public static ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = slow.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode l = mergeSort(slow.next);
        slow.next = null;
        ListNode r = mergeSort(head);
        return mergeListSort(l, r);
    }

    private static ListNode mergeListSort(ListNode l, ListNode r) {
        ListNode p1 = l;
        ListNode p2 = r;
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return head.next;
    }

    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = head.next;
        ListNode first = new ListNode(Integer.MIN_VALUE);
        first.next = head;
        head.next = null;
        ListNode p1 = first;
        while (p != null) {
            ListNode temp = p.next;
            p1 = first;
            while (p1.next != null && p1.next.val < p.val)
                p1 = p1.next;
            if (p1.next == null) {
                p.next = null;
                p1.next = p;
            } else {
                ListNode p1n = p1.next;
                p1.next = p;
                p.next = p1n;
            }
            p = temp;
        }
        return first.next;
    }
}
